package com.bascker.algorithm.practice.search.dfs.lexica_order;

import java.util.ArrayList;
import java.util.List;

class Solution {

    public List<Integer> lexicalOrder(int n) {
        List<Integer> ret = new ArrayList<>();

        // 从 [1, 9] 进行 dfs 检索
        for (int i = 1; i <= 9; i ++) {
            dfs(ret, i, n);
        }

        return ret;
    }

    private void dfs(List<Integer> ret, int i, int n) {
        if (i > n) {
            return;
        }

        ret.add(i);
        // 按字典序继续搜索压入数据, 如 n = 13，则 1 -> 11 -> 12 -> 13
        for (int j = 0; j <= 9; j ++) {
            dfs(ret, i * 10 + j, n);
        }
    }

}
